//给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 
//
// 你可以假设数组中无重复元素。 
//
// 示例 1: 
//
// 输入: [1,3,5,6], 5
//输出: 2
// 
//
// 示例 2: 
//
// 输入: [1,3,5,6], 2
//输出: 1
// 
//
// 示例 3: 
//
// 输入: [1,3,5,6], 7
//输出: 4
// 
//
// 示例 4: 
//
// 输入: [1,3,5,6], 0
//输出: 0
// 
// Related Topics 数组 二分查找 
// 👍 738 👎 0

package com.everyday.algorithm.changyf.leetcode.editor.cn;
public class SearchInsertPosition {
    public static void main(String[] args) {
        Solution solution = new SearchInsertPosition().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //使用二分查找搜索插入位置
    public int searchInsert(int[] nums, int target) {
        //数组长度为0，直接返回0
        if (nums.length == 0){
            return 0;
        }
        //开始位置指针
        int start = 0;
        //结束位置指针
        int end = nums.length -1;
        //中间位置
        int mid;
        while (true) {
            //start大于end说明到达搜索终点
            if (start > end){
                return start;
            }
            //取中间索引
            mid = (start + end)/2;
            if (target > nums[mid]) {
                start = mid + 1;
            } else if (target < nums[mid]) {
                end = mid - 1;
            } else {//因为假设没有重复
                return mid;
            }
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}